#include "heap.h"



Node* heap::find_min(){return (Node*)NULL;}//O(n), leave it for now
Node* heap::find_max()
{
        return root;
}


void heap::upHeap(Node* n){
        if(n->parent != NULL && n->parent->val < n->val)
        {
                swap(n, n->parent);
                upHeap(n->parent);
        }
}


void heap::downHeap(Node* n){
        if(n->left != NULL && n->val < n->left->val)
        {
                swap(n, n->left);
                downHeap(n->left);
        }
        else if(n->right != NULL && n->val < n->right->val)
        {
                swap(n, n->right);
                downHeap(n->right);
        }
}


void heap::swap(Node* n1, Node* n2){
        int temp = n1->val;
        n1->val = n2->val;
        n2->val = temp;
}


void heap::insert(int val){
        Node* myNode = new Node(NULL, NULL, NULL, val);
        unsigned int cur_node_cnt = getNodecnt();
        if(root == NULL)
        {
                root = myNode;
        }
        else
        {
                const unsigned int parent_idx = (cur_node_cnt + 1) / 2;
                Node* parent_node = quickLU[parent_idx];
                if(parent_node->left == NULL)
                {
                        parent_node->left = myNode;
                        myNode->parent = parent_node;
                }
                else
                {
                        parent_node->right = myNode;
                        myNode->parent = parent_node;
                }
                
                upHeap(myNode);
        }
        
        increNodecnt();
        quickLU.insert(make_pair(cur_node_cnt + 1, myNode));
}


Node* heap::search(int val){
        queue<Node*> myQ;
        if(val > root->val)
                return (Node*)NULL;
        else if(val == root->val)
                return root;
        else
        {
                if(root->left->val > val)
                        myQ.push(root->left);
                else if(root->left->val == val)
                        return root->left;

                if(root->right->val > val)
                        myQ.push(root->right);
                else if(root->right->val == val)
                        return root->right;
                
                while(!myQ.empty()){
                        Node* cur = myQ.front();
                        if(cur->left->val > val)
                                myQ.push(cur->left);
                        else if(cur->left->val == val)
                                return cur->left;
                        
                        if(cur->right->val > val)
                                myQ.push(cur->right);
                        else if(cur->right->val == val)
                                return cur->right;
                        myQ.pop();
                }
                
                return (Node*)NULL;
        }        
}


bool heap::remove(int val){
        Node* myNode = search(val);
        unsigned int cur_node_cnt = getNodecnt();
        if(myNode == NULL)
        {
                cout << "Requested node for deletion not found!" << endl;
                return false;
        }
        else
        {
                Node* node_for_switch = quickLU[cur_node_cnt];
                swap(node_for_switch, myNode);
                if(node_for_switch->val < myNode->val)
                        upHeap(myNode);
                else
                        downHeap(myNode);
                
                if(node_for_switch->parent != NULL)
                {
                        if(node_for_switch->parent->right == node_for_switch)
                                node_for_switch->parent->right = NULL;
                        if(node_for_switch->parent->left == node_for_switch)
                                node_for_switch->parent->left = NULL;
                }
                else
                {
                        root = NULL;//empty tree
                }
                
                delete node_for_switch;
                decreNodecnt();
                quickLU.erase(cur_node_cnt);
                return true;
        }
}


void heap::destroy(){
        if(root == NULL)
                return;
        
        //method 1 
        destroy(root);
        
        //method 2
        /*
        queue<Node*> myQ;
        myQ.push(root);
        while(!myQ.empty()){
                Node* myNode = myQ.front();
                if(myNode->left != NULL)
                        myQ.push(myNode->left);
                if(myNode->right != NULL)
                        myQ.push(myNode->right);
                delete myNode;
                myQ.pop();
        }
        */
}


void heap::destroy(Node* leaf){
        if(leaf == NULL)
                return;
        
        destroy(leaf->left);
        destroy(leaf->right);
        delete leaf;
}


void heap::print(){
        if(root == NULL)
                return;
        
        Node* empty_node = new Node(NULL, NULL, NULL, -1);
        int flag = 0, i = 1, level = 0;
        queue<int> valQ;
        queue<Node*> myQ;
        myQ.push(root);
        valQ.push(root->val);
        while(!myQ.empty()){
                Node* myNode = myQ.front();
                //cout << "haha " << myNode->val << endl;
                if(myNode->left != NULL){
                        flag = 1;
                        myQ.push(myNode->left);
                        valQ.push(myNode->left->val);
                }
                else{
                        myQ.push(empty_node);
                        valQ.push(-1);
                }
                
                if(myNode->right != NULL){
                        flag = 1;
                        myQ.push(myNode->right);
                        valQ.push(myNode->right->val);
                }
                else{
                        myQ.push(empty_node);
                        valQ.push(-1);
                }
                
                if(i == pow(2, level)){
                        if(flag == 1)
                                level++;
                        else{
                                //cout << "hoho" << endl;
                                break;
                        }
                        flag = 0;
                        i = 1;
                }
                else
                        i++;
                
                myQ.pop();
        }

        const int total_level = level;
        cout << "Total level is " << total_level << endl;
        
        i = 1;
        level = 0;
        unsigned int indent = pow(2, (total_level - level)) - 1;
        unsigned int underline_len = pow(2, (total_level - level + 1));
        cout << string(indent, ' ');
        while(!valQ.empty()){
                int val = valQ.front();
                unsigned int interval = pow(2, (total_level - level + 1)) - 1;
                if(val != -1)
                        cout << val << string(interval, ' ');
                else
                        cout << string(interval + 1, ' ');
                if(i == pow(2, level)){
                        cout << endl;
                        cout << string(underline_len, '-') << endl;
                        if(level == total_level)
                                break;
                        level++;
                        if(level != total_level){
                                indent = pow(2, (total_level - level)) - 1;
                                cout << string(indent, ' ');
                        }
                        i = 1;
                }
                else
                        i++;
                valQ.pop();
        }
        
        delete empty_node;
}


int main (int argc, char* argv[]){        
        heap* BT = new heap;
        
        BT->insert(10);
        BT->remove(10);
        BT->insert(10);
        BT->insert(7);
        BT->insert(3);
        BT->insert(13);
        BT->insert(19);
        BT->insert(18);
        BT->insert(17);
        BT->insert(5);
        BT->insert(73);
        BT->insert(31);
        BT->insert(45);
        BT->insert(57);
        BT->insert(63);
        BT->insert(8);
        BT->insert(14);
        BT->print();
        
        BT->remove(5);
        //BT->remove(13);
        BT->print();
        
        BT->insert(35);
        BT->insert(43);
        BT->insert(33);
        BT->insert(22);
        BT->insert(77);
        BT->insert(13);
        BT->insert(4);
        BT->print();
        
        return 0;
}
